{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #二叉树的右视图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rightSideView"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的右视图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树的 <strong>根节点</strong> <code>root</code>，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/02/14/tree.jpg\" style=\"width: 270px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>&nbsp;[1,2,3,null,5,null,4]\n",
    "<strong>输出:</strong>&nbsp;[1,3,4]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>&nbsp;[1,null,3]\n",
    "<strong>输出:</strong>&nbsp;[1,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>&nbsp;[]\n",
    "<strong>输出:</strong>&nbsp;[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树的节点个数的范围是 <code>[0,100]</code></li>\n",
    "\t<li><meta charset=\"UTF-8\" /><code>-100&nbsp;&lt;= Node.val &lt;= 100</code>&nbsp;</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 199&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/binary-tree-right-side-view/\">https://leetcode-cn.com/problems/binary-tree-right-side-view/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [WNC0Lk](https://leetcode.cn/problems/WNC0Lk/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [WNC0Lk](https://leetcode.cn/problems/WNC0Lk/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        target=[]\n",
    "        l=[]\n",
    "        if root is None:\n",
    "            return l\n",
    "        l.append(root)\n",
    "        while len(l):\n",
    "            length=len(l)\n",
    "            if l[len(l)-1] is not None:\n",
    "                target.append(l[len(l)-1].val)\n",
    "            \n",
    "            for _ in range(length):\n",
    "                node=l.pop(0)\n",
    "                if node is  not None:\n",
    "                    if node.left is not None:\n",
    "                        l.append(node.left)\n",
    "                    if node.right is not None:\n",
    "                        l.append(node.right)\n",
    "        return target\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root :return []\n",
    "        q = collections.deque()\n",
    "        q.append(root)\n",
    "        res = [root.val]\n",
    "\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            temp = []\n",
    "            for _ in range(size):\n",
    "                node = q.popleft()\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                    temp.append(node.left.val)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                    temp.append(node.right.val)\n",
    "            if temp:\n",
    "                res.append(temp[-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        if not root:\n",
    "            return []\n",
    "        while queue:\n",
    "            level = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                level.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(level[-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root: return []\n",
    "        queue = [root]\n",
    "        output = []\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                head = queue.pop(0)\n",
    "                temp = head.val\n",
    "                if head.left: queue.append(head.left)\n",
    "                if head.right: queue.append(head.right)\n",
    "            output.append(temp)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        q = []\n",
    "        ans = []\n",
    "        q.append(root)\n",
    "        size = 1\n",
    "        while len(q) > 0:\n",
    "            node = q.pop(0)\n",
    "            print(node.val)\n",
    "            size -= 1\n",
    "            if node.left is not None:\n",
    "                q.append(node.left)\n",
    "            if node.right is not None:\n",
    "                q.append(node.right)\n",
    "            if size == 0:\n",
    "                ans.append(node.val)\n",
    "                size = len(q)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        queue,ret = deque(),[]\n",
    "        if root:\n",
    "            queue.append(root)\n",
    "        while queue:\n",
    "            lg = len(queue)\n",
    "            for i in range(lg):\n",
    "                q = queue.popleft()\n",
    "                if i == lg - 1:\n",
    "                    ret.append(q.val)\n",
    "                if q.left:\n",
    "                    queue.append(q.left)\n",
    "                if q.right:\n",
    "                    queue.append(q.right)\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        q = []\n",
    "        ans = []\n",
    "        q.append(root)\n",
    "        size = 1\n",
    "        while len(q) > 0:\n",
    "            node = q.pop(0)\n",
    "            size -= 1\n",
    "            if node.left is not None:\n",
    "                q.append(node.left)\n",
    "            if node.right is not None:\n",
    "                q.append(node.right)\n",
    "            if size == 0:\n",
    "                ans.append(node.val)\n",
    "                size = len(q)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        from collections import deque\n",
    "        que = deque([root])\n",
    "        res = []\n",
    "        while que:\n",
    "            size = len(que)\n",
    "            depth_list = []\n",
    "            for _ in range(size):\n",
    "                cur = que.popleft()\n",
    "                depth_list.append(cur.val)\n",
    "                if cur.left:\n",
    "                    que.append(cur.left)\n",
    "                if cur.right:\n",
    "                    que.append(cur.right)\n",
    "            res.append(depth_list[-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        q = deque([root])\n",
    "        res = []\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                node = q.popleft()\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            res.append(node.val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        res=[]\n",
    "        queue=[]\n",
    "        if not root:\n",
    "            return res\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            size=len(queue)\n",
    "            while size>0:\n",
    "                node=queue.pop(0)\n",
    "                if size==1:\n",
    "                    res.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "\n",
    "                size-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        ans = []\n",
    "        def dfs(node,depth):\n",
    "            if not node:\n",
    "                return\n",
    "            if depth == len(ans):\n",
    "                ans.append(node.val)\n",
    "            dfs(node.right,depth+1)\n",
    "            dfs(node.left,depth+1)\n",
    "        dfs(root,0)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        st,ans=[],[]\n",
    "        st.append(root)\n",
    "        while st:\n",
    "            lenth=len(st)\n",
    "            ans.append(st[-1].val)\n",
    "            while lenth:\n",
    "                node=st.pop(0)\n",
    "                if node.left:\n",
    "                    st.append(node.left)\n",
    "                if node.right:\n",
    "                    st.append(node.right)\n",
    "                lenth-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def rightSideView(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return []\n",
    "        L=root\n",
    "        ans=list()\n",
    "        quee=[L]\n",
    "        nextquee=list()\n",
    "        while quee!=[]:\n",
    "            for i in quee:\n",
    "                if i.left!=None:\n",
    "                    nextquee.append(i.left)\n",
    "                if i.right!=None:\n",
    "                    nextquee.append(i.right)\n",
    "            last=quee.pop()\n",
    "            ans.append(last.val)\n",
    "            quee=nextquee[:]\n",
    "            nextquee=list()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        queue = []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            next_queue = []\n",
    "            ans = []\n",
    "            for node in queue:\n",
    "                ans.append(node.val)\n",
    "                if node.left: next_queue.append(node.left)\n",
    "                if node.right: next_queue.append(node.right)\n",
    "            res.append(ans[-1])\n",
    "            queue = next_queue\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        from collections import deque\n",
    "\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        res = []\n",
    "        queue = deque([root])\n",
    "\n",
    "        while queue:\n",
    "            res.append(queue[-1].val)\n",
    "\n",
    "            for _ in range(len(queue)):\n",
    "                head = queue.popleft()\n",
    "                if head.left:\n",
    "                    queue.append(head.left)\n",
    "                if head.right:\n",
    "                    queue.append(head.right)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root: return []\n",
    "        que, layerRight = deque(), {}\n",
    "        que.append((0, root))\n",
    "        while(que):\n",
    "            layer, node = que.popleft()\n",
    "            layerRight[layer] = node.val\n",
    "            if node.left:que.append((1+layer, node.left))\n",
    "            if node.right:que.append((1+layer, node.right))\n",
    "        res = [i for i in layerRight.items()]\n",
    "        res.sort()\n",
    "        return [i[1] for i in res]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        # queue = [[root]]\n",
    "        # while len(queue)>0:\n",
    "        #     cur_layer = queue.pop(0)\n",
    "        #     tmp = []\n",
    "        #     for i in range(len(cur_layer)):\n",
    "        #         if i == len(cur_layer)-1:\n",
    "        #             res.append(cur_layer[i].val)\n",
    "        #         if cur_layer[i].left:\n",
    "        #             tmp.append(cur_layer[i].left)\n",
    "        #         if cur_layer[i].right:\n",
    "        #             tmp.append(cur_layer[i].right)\n",
    "        #     if len(tmp)>0:\n",
    "        #         queue.append(tmp)\n",
    "        # return res\n",
    "        def dfs(node, depth):\n",
    "            if not node:return\n",
    "            if depth == len(res):\n",
    "                res.append(node.val)\n",
    "            dfs(node.right, depth + 1)\n",
    "            dfs(node.left, depth + 1)\n",
    "        dfs(root, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = []\n",
    "        queue = [root]\n",
    "        cnt = 1\n",
    "        while queue:\n",
    "            for i in range(cnt):\n",
    "                target = queue[0]\n",
    "                if i == cnt - 1:\n",
    "                    ans.append(target.val)\n",
    "                queue.pop(0)\n",
    "                if target.left:\n",
    "                    queue.append(target.left)\n",
    "                if target.right:\n",
    "                    queue.append(target.right)\n",
    "            cnt = len(queue)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode):\n",
    "        if root is None:\n",
    "            return []\n",
    "        queue=[root]\n",
    "        ret=[]\n",
    "        while queue:\n",
    "            length=len(queue)\n",
    "            for i in range(length):\n",
    "                cur=queue.pop(0)\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "                if i==length-1:\n",
    "                    ret.append(cur.val)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        rightmost_value_at_depth = dict() # 深度为索引，存放节点的值\n",
    "        max_depth = -1\n",
    "\n",
    "        stack = [(root, 0)]\n",
    "        while stack:\n",
    "            node, depth = stack.pop()\n",
    "\n",
    "            if node is not None:\n",
    "                # 维护二叉树的最大深度\n",
    "                max_depth = max(max_depth, depth)\n",
    "\n",
    "                # 如果不存在对应深度的节点我们才插入\n",
    "                rightmost_value_at_depth.setdefault(depth, node.val)\n",
    "\n",
    "                stack.append((node.left, depth + 1))\n",
    "                stack.append((node.right, depth + 1))\n",
    "\n",
    "        return [rightmost_value_at_depth[depth] for depth in range(max_depth + 1)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        ans = []\n",
    "        queue = deque()\n",
    "        if not root:\n",
    "            return ans\n",
    "        queue.append(root)\n",
    "        while len(queue) > 0:\n",
    "            n = len(queue)\n",
    "            ans.append(queue[n-1].val)\n",
    "            for i in range(n):\n",
    "                cur = queue.popleft()\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        rightmost_value_at_depth = dict() # 深度为索引，存放节点的值\n",
    "        max_depth = -1\n",
    "\n",
    "        stack = [(root, 0)]\n",
    "        while stack:\n",
    "            node, depth = stack.pop()\n",
    "\n",
    "            if node is not None:\n",
    "                # 维护二叉树的最大深度\n",
    "                max_depth = max(max_depth, depth)\n",
    "\n",
    "                # 如果不存在对应深度的节点我们才插入\n",
    "                rightmost_value_at_depth.setdefault(depth, node.val)\n",
    "\n",
    "                stack.append((node.left, depth + 1))\n",
    "                stack.append((node.right, depth + 1))\n",
    "\n",
    "        return [rightmost_value_at_depth[depth] for depth in range(max_depth + 1)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        rightmost_value_at_depth = dict() # 深度为索引，存放节点的值\n",
    "        max_depth = -1\n",
    "\n",
    "        queue = deque([(root, 0)])\n",
    "        while queue:\n",
    "            node, depth = queue.popleft()\n",
    "\n",
    "            if node is not None:\n",
    "                # 维护二叉树的最大深度\n",
    "                max_depth = max(max_depth, depth)\n",
    "\n",
    "                # 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可\n",
    "                rightmost_value_at_depth[depth] = node.val\n",
    "\n",
    "                queue.append((node.left, depth + 1))\n",
    "                queue.append((node.right, depth + 1))\n",
    "\n",
    "        return [rightmost_value_at_depth[depth] for depth in range(max_depth + 1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if root == None:\n",
    "            return []\n",
    "        \n",
    "        stack = [root]\n",
    "        res = []\n",
    "        while len(stack) > 0:\n",
    "            tmp = []\n",
    "            for node in stack:\n",
    "                if node.left:\n",
    "                    tmp.append(node.left)\n",
    "                if node.right:\n",
    "                    tmp.append(node.right)\n",
    "            res.append(stack[-1].val)\n",
    "            stack = tmp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        queue = collections.deque([root])\n",
    "        right_view = []\n",
    "\n",
    "        while queue:\n",
    "            level_size = len(queue)\n",
    "            for i in range(len(queue)):\n",
    "                cur = queue.popleft()\n",
    "                if i == level_size - 1:\n",
    "                    right_view.append(cur.val)\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "        return right_view\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        quene = collections.deque([root])  # 队列，先入先出\n",
    "        res = []\n",
    "        while quene:\n",
    "            lst = []\n",
    "            for i in range(len(quene)):\n",
    "                node = quene.popleft()\n",
    "                lst.append(node.val)\n",
    "                if node.left:\n",
    "                    quene.append(node.left)\n",
    "                if node.right:\n",
    "                    quene.append(node.right)\n",
    "            res.append(lst[-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        res = []\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "\n",
    "            for i in range(size):\n",
    "                r = queue.pop(0)\n",
    "\n",
    "                if i == size-1:\n",
    "                   res.append(r.val)\n",
    "\n",
    "                if r.left:\n",
    "                    queue.append(r.left)\n",
    "\n",
    "                if r.right:\n",
    "                    queue.append(r.right)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if root is None: return []\n",
    "        queue = [root]\n",
    "        res = []\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            cur_layuer_len = len(queue)\n",
    "            for i in range(cur_layuer_len):\n",
    "                cur_node = queue.pop(0)\n",
    "                tmp.append(cur_node.val)\n",
    "                if cur_node.left: queue.append(cur_node.left)\n",
    "                if cur_node.right: queue.append(cur_node.right)\n",
    "            res.append(tmp)\n",
    "        right_view_res = []\n",
    "        for layer_res in res:\n",
    "            right_view_res.append(layer_res[-1])\n",
    "        return right_view_res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        # 层序遍历 每一层只记录最后一个节点！（最好的解法）\n",
    "        if not root: return []\n",
    "        res = []\n",
    "        que = [root]\n",
    "        while que: \n",
    "            length = len(que)\n",
    "            for i in range(length):\n",
    "                cur = que.pop(0)\n",
    "                if i == length - 1: \n",
    "                    res.append(cur.val)\n",
    "                if cur.left: que.append(cur.left)\n",
    "                if cur.right: que.append(cur.right)\n",
    "        return res\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            len_queue = len(queue)\n",
    "            for i in range(len_queue):\n",
    "                node =queue.popleft()\n",
    "                if i==len_queue-1:\n",
    "                    res.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        queue = [[root]]\n",
    "        while len(queue)>0:\n",
    "            cur_layer = queue.pop(0)\n",
    "            tmp = []\n",
    "            for i in range(len(cur_layer)):\n",
    "                if i == len(cur_layer)-1:\n",
    "                    res.append(cur_layer[i].val)\n",
    "                if cur_layer[i].left:\n",
    "                    tmp.append(cur_layer[i].left)\n",
    "                if cur_layer[i].right:\n",
    "                    tmp.append(cur_layer[i].right)\n",
    "            if len(tmp)>0:\n",
    "                queue.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        ans=[]\n",
    "        if root == None:\n",
    "            return ans\n",
    "        \n",
    "        my_queue = deque()\n",
    "        my_queue.append(root)\n",
    "        while(len(my_queue) != 0):\n",
    "            length = len(my_queue)\n",
    "            ans.append(my_queue[-1].val)\n",
    "            for i in range(len(my_queue)):\n",
    "                item = my_queue[0]\n",
    "                my_queue.popleft()\n",
    "                if(item.left != None):\n",
    "                    my_queue.append(item.left)\n",
    "                if(item.right != None):\n",
    "                    my_queue.append(item.right)\n",
    "                \n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if root==None:\n",
    "            return []\n",
    "        q = deque([root])\n",
    "        res = []\n",
    "        while q:\n",
    "            tmp = len(q)\n",
    "            for i in range(tmp):\n",
    "                node = q.popleft()\n",
    "                if i==tmp-1:\n",
    "                    res.append(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        dct = {}\n",
    "        \n",
    "        que = deque([(root, 1)])\n",
    "        max_depth = -1\n",
    "        while(len(que) != 0):\n",
    "            node, depth = que.popleft()\n",
    "            if node is not None:\n",
    "                max_depth = max(depth, max_depth)\n",
    "                dct[depth] = node.val\n",
    "\n",
    "                que.append((node.left, depth+1))\n",
    "                que.append((node.right, depth+1))\n",
    "\n",
    "        return [dct[depth] for depth in range(1, max_depth+1)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        if not root:\n",
    "            return ans\n",
    "            \n",
    "        que = collections.deque([root])\n",
    "        while que:\n",
    "            length = len(que)\n",
    "            for _ in range(length):\n",
    "                cur = que.popleft()\n",
    "                if cur.left:\n",
    "                    que.append(cur.left)\n",
    "                if cur.right:\n",
    "                    que.append(cur.right)                    \n",
    "                if _ == length - 1:\n",
    "                    ans.append(cur.val)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        ans = []\n",
    "        def dfs(node:Optional[TreeNode], depth:int)->None:\n",
    "            if not node: return \n",
    "            if depth ==len(ans):\n",
    "                ans.append(node.val)\n",
    "            dfs(node.right,depth+1)\n",
    "            dfs(node.left,depth+1)\n",
    "        dfs(root,0)\n",
    "        return ans\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        ans = [] # 存储结果\n",
    "        def dfs(root,depth):\n",
    "            if not root:\n",
    "                return \n",
    "            if len(ans) == depth:\n",
    "                ans.append(root.val)\n",
    "            if root.right:\n",
    "                dfs(root.right,depth+1)\n",
    "            if root.left:\n",
    "                dfs(root.left,depth+1)\n",
    "        dfs(root,0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "#         ans = []\n",
    "#         def dfs(node: Optional[TreeNode],k:int)->List[int]:\n",
    "#             if not node:return \n",
    "#             # 特例：不存在的情况\n",
    "#             # 存入情况，当深度首次到达\n",
    "#             if k==len(ans):\n",
    "#                 ans.append(node.val)\n",
    "#             dfs(node.right,k+1)\n",
    "#             dfs(node.left,k+1)\n",
    "#         dfs(root,0)\n",
    "#         return ans\n",
    "            \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root: return []\n",
    "        import collections\n",
    "        queue = collections.deque()\n",
    "        res = []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            ans = []\n",
    "            nextlist = []\n",
    "\n",
    "            for node in queue:\n",
    "                # print(node)\n",
    "                ans.append(node.val)\n",
    "                if node.left:\n",
    "                    nextlist.append(node.left)\n",
    "                if node.right:\n",
    "                    nextlist.append(node.right)\n",
    "            queue.clear()\n",
    "            queue = collections.deque(nextlist)\n",
    "            res.append(ans[-1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        rightmostValAtDepth = dict()\n",
    "        maxDepth = -1\n",
    "\n",
    "        stack = [(root, 0)]\n",
    "        while stack:\n",
    "            node, depth = stack.pop()\n",
    "\n",
    "            if node is not None:\n",
    "                maxDepth = max(maxDepth, depth)\n",
    "\n",
    "                rightmostValAtDepth.setdefault(depth, node.val)\n",
    "\n",
    "                stack.append((node.left, depth + 1))\n",
    "                stack.append((node.right, depth + 1))\n",
    "\n",
    "        \n",
    "\n",
    "        return [ rightmostValAtDepth[depth] for depth in range (maxDepth + 1) ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root: return []\n",
    "        queue = deque([root])\n",
    "        res = []\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            for i in range(length):\n",
    "                node = queue.popleft()\n",
    "                if i == length - 1:\n",
    "                    res.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        q = collections.deque()\n",
    "        if not root:\n",
    "            return []\n",
    "        q.append([root, 0])\n",
    "        ans = []\n",
    "        while q:\n",
    "            node, layer = q.popleft()\n",
    "            if len(q) == 0 or q[0][1] != layer:\n",
    "                ans.append(node.val)\n",
    "            if node.left:\n",
    "                q.append([node.left, layer + 1])\n",
    "            if node.right:\n",
    "                q.append([node.right, layer + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root):\n",
    "        ret = []\n",
    "        queue = deque()\n",
    "        if root:\n",
    "            queue.append(root)\n",
    "        while queue:\n",
    "            lg = len(queue)\n",
    "            for i in range(lg):\n",
    "\n",
    "                q = queue.popleft()\n",
    "                if i == lg -1:\n",
    "                    ret.append(q.val)\n",
    "                if q.left:\n",
    "                    queue.append(q.left)\n",
    "                if q.right:\n",
    "                    queue.append(q.right)\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        view_values = []\n",
    "        old_queue = []\n",
    "        new_queue = [root]\n",
    "        while new_queue:\n",
    "            old_queue = new_queue\n",
    "            new_queue = []\n",
    "            while old_queue:\n",
    "                node = old_queue.pop(0)\n",
    "                if node.left:\n",
    "                    new_queue.append(node.left)\n",
    "                if node.right:\n",
    "                    new_queue.append(node.right)\n",
    "            view_values.append(node.val)\n",
    "        return view_values\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        ans = []\n",
    "        max_depth = -1\n",
    "        stack = [(root, 0)]\n",
    "        tree_level_map = {}\n",
    "        while stack:\n",
    "            node, depth = stack.pop()\n",
    "            if node:\n",
    "                max_depth = max(max_depth, depth)\n",
    "\n",
    "                tree_level_map[depth] = node\n",
    "                stack.append((node.right, depth + 1))\n",
    "                stack.append((node.left, depth + 1))\n",
    "\n",
    "        return [tree_level_map[depth].val for depth in range(max_depth + 1)]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = []\n",
    "        def dfs(node: Optional[TreeNode], depth: int) -> None:\n",
    "            if node is None: return\n",
    "            if depth == len(ans):  # 这个深度首次遇到\n",
    "                ans.append(node.val)\n",
    "            dfs(node.right, depth + 1)  # 先递归右子树，保证首次遇到的一定是最右边的节点\n",
    "            dfs(node.left, depth + 1)\n",
    "        dfs(root, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        observe_set = []\n",
    "        if not root:\n",
    "            return []\n",
    "        parent_set = [root]\n",
    "        children_set = []\n",
    "        while parent_set:\n",
    "            for parent in parent_set:\n",
    "                if parent.left:\n",
    "                    children_set.append(parent.left)\n",
    "                if parent.right:\n",
    "                    children_set.append(parent.right)\n",
    "            observe_set.append(parent_set[-1].val)\n",
    "            parent_set = children_set\n",
    "            children_set = []\n",
    "        return observe_set\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "\n",
    "        return bfs(root)\n",
    "\n",
    "def bfs(root):\n",
    "    queue = [root]\n",
    "    res = []\n",
    "    while len(queue) > 0:\n",
    "        l = len(queue)\n",
    "        res.append(queue[0].val)\n",
    "        for i in range(l):\n",
    "            # 先添加右节点，再添加左节点\n",
    "            if queue[i].right is not None:\n",
    "                queue.append(queue[i].right)\n",
    "            if queue[i].left is not None:\n",
    "                queue.append(queue[i].left)\n",
    "        queue = queue[l:]\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from queue import Queue\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        ans = []\n",
    "        if not root:\n",
    "            return ans\n",
    "        q = Queue()\n",
    "        q.put(root)\n",
    "\n",
    "        while not q.empty():\n",
    "            n = q.qsize()\n",
    "            for i in range(n):\n",
    "                node = q.get()\n",
    "                if node.left:\n",
    "                    q.put(node.left)\n",
    "                if node.right:\n",
    "                    q.put(node.right)\n",
    "                if i == n - 1:\n",
    "                    ans.append(node.val)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        #返回每一层最右侧的节点\n",
    "        if root == None:\n",
    "            return []\n",
    "        ret = []\n",
    "        queue = []\n",
    "        queue.append(root)\n",
    "        while len(queue)!=0:\n",
    "            size = len(queue)\n",
    "            level = []\n",
    "            for i in range (0,size):\n",
    "                node = queue[0]\n",
    "                level.append(node.val)\n",
    "                queue.pop(0)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            ret.append(level)\n",
    "        result = []\n",
    "        for each in ret:\n",
    "            result.append(each[-1])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        ans = []\n",
    "        queue = deque()\n",
    "        if not root:\n",
    "            return ans\n",
    "        queue.append(root)\n",
    "        while len(queue) > 0:\n",
    "            n = len(queue)\n",
    "            for i in range(n):\n",
    "                cur = queue.popleft()\n",
    "                if i == n-1:\n",
    "                    ans.append(cur.val)\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        mapping = {}\n",
    "        def postDfs(root,path,level):\n",
    "            if root:\n",
    "                if level not in mapping:\n",
    "                    res.append(root.val)\n",
    "                mapping[level] = root\n",
    "                postDfs(root.right,path,level+1)\n",
    "                postDfs(root.left,path,level+1)\n",
    "        res = []\n",
    "        postDfs(root,[],0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        res = []\n",
    "        if root is None:\n",
    "            return res\n",
    "        q = Queue()\n",
    "        q.put((root,0))\n",
    "        cur_level = -1\n",
    "        while not q.empty():\n",
    "            node, level = q.get()\n",
    "            if level > cur_level:\n",
    "                res.append(node.val)\n",
    "                cur_level = level\n",
    "            if node.right:\n",
    "                q.put((node.right, level+1))\n",
    "            if node.left:\n",
    "                q.put((node.left, level+1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        res = []\n",
    "        queue = []\n",
    "        if not root:\n",
    "            return res\n",
    "        queue = [root]\n",
    "        # print(queue)\n",
    "    # bfs\n",
    "        while len(queue) > 0:\n",
    "            n = len(queue)\n",
    "            res.append(queue[n-1].val)\n",
    "            for i in range(n):\n",
    "                cur = queue[0]\n",
    "                queue = queue[1:]\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        # res = []\n",
    "        # level = [root]\n",
    "        # while root and level:\n",
    "        #     res.append(level[-1].val)\n",
    "        #     level = [y for x in level for y in (x.left, x.right) if y]\n",
    "        # return res\n",
    "        res = []\n",
    "        def dfs(node, H, curH, res):\n",
    "            if not node:\n",
    "                return curH\n",
    "            if H > curH:\n",
    "                res.append(node.val)\n",
    "                curH = H\n",
    "            curH = dfs(node.right, H+1, curH, res)\n",
    "            curH = dfs(node.left, H+1, curH, res)\n",
    "            return curH\n",
    "        dfs(root, 0, -1, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        result = [root.val]\n",
    "        que = [root]\n",
    "\n",
    "        while que:\n",
    "            leaves = []\n",
    "            for node in que:\n",
    "                if node.left:\n",
    "                    leaves.append(node.left)\n",
    "                if node.right:\n",
    "                    leaves.append(node.right)\n",
    "            if leaves:\n",
    "                result.append(leaves[-1].val)\n",
    "            que = leaves\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        dct = {}\n",
    "        if(root is None):\n",
    "            return []\n",
    "        que = deque([(root, 1)])\n",
    "        max_depth = 1\n",
    "        while len(que)>0:\n",
    "            node, depth = que.popleft() \n",
    "            \n",
    "            if node is not None:\n",
    "                \n",
    "                max_depth = max(depth, max_depth)\n",
    "                dct[depth] = node.val\n",
    "                \n",
    "                que.append((node.left,depth+1))\n",
    "                que.append((node.right, depth+1))\n",
    "        \n",
    "        return [dct[depth] for depth in range(1,max_depth+1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        ans = []\n",
    "        if not root:\n",
    "            return ans\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            ans.append(q[0].val)\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        right = []\n",
    "        if not root:\n",
    "            return right\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            n, level = len(queue), 0\n",
    "            for i in range(n):\n",
    "                node = queue.popleft()\n",
    "                level = node.val\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            right.append(level)\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        ans = []\n",
    "        def dfs(node: Optional[TreeNode],k:int)->List[int]:\n",
    "            if not node:return \n",
    "            # 特例：不存在的情况\n",
    "            # 存入情况，当深度首次到达\n",
    "            if k==len(ans):\n",
    "                ans.append(node.val)\n",
    "            dfs(node.right,k+1)\n",
    "            dfs(node.left,k+1)\n",
    "        dfs(root,0)\n",
    "        return ans\n",
    "            \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        ans=[]\n",
    "        def dfs(root,cnt) :\n",
    "            if root==None :\n",
    "                return\n",
    "            if cnt==len(ans) :\n",
    "                ans.append(root.val)\n",
    "            dfs(root.right,cnt+1)\n",
    "            dfs(root.left,cnt+1)\n",
    "        dfs(root,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        queue,res = deque(),[]\n",
    "        if not root:return []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            for i in range(n):\n",
    "                temp = queue.popleft()\n",
    "                if i == n-1:\n",
    "                    res.append(temp.val)\n",
    "                if temp.left:\n",
    "                    queue.append(temp.left)\n",
    "                if temp.right:\n",
    "                    queue.append(temp.right)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        output=[]\n",
    "        def dfs(root,depth):\n",
    "            if not root:\n",
    "                return\n",
    "            if depth==len(output):\n",
    "                output.append(root.val)\n",
    "            dfs(root.right,depth+1)\n",
    "            dfs(root.left,depth+1)\n",
    "        dfs(root,0)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res=[]\n",
    "        que=[]\n",
    "        que.append(root)\n",
    "        res.append(root.val)\n",
    "        cl=1\n",
    "        nl=0\n",
    "        while que:\n",
    "            node=que.pop(0)\n",
    "            cl-=1\n",
    "            if node.left:\n",
    "                que.append(node.left)\n",
    "                nl+=1\n",
    "            if node.right:\n",
    "                que.append(node.right)\n",
    "                nl+=1\n",
    "            if cl==0:\n",
    "                if nl!=0:\n",
    "                    res.append(que[-1].val)\n",
    "                cl=nl\n",
    "                nl=0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        res = []\n",
    "        queue = deque([root])\n",
    "\n",
    "        while queue:\n",
    "            lens = len(queue)\n",
    "\n",
    "            for i in range(lens):\n",
    "                node = queue.popleft()\n",
    "\n",
    "                if i == lens - 1:\n",
    "                    res.append(node.val)\n",
    "                \n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                \n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        \n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ret_list = []\n",
    "        buffer = []\n",
    "\n",
    "        queue = deque()\n",
    "        current_idx = 0\n",
    "        queue.append((root, current_idx))\n",
    "\n",
    "        while queue:\n",
    "            node, idx = queue.popleft()\n",
    "            if idx != current_idx:\n",
    "                ret_list.append(buffer[-1])\n",
    "                buffer = [node.val]\n",
    "                current_idx = idx\n",
    "            else:\n",
    "                buffer.append(node.val)\n",
    "            if node.left:\n",
    "                queue.append((node.left, idx + 1))\n",
    "            if node.right:\n",
    "                queue.append((node.right, idx + 1))\n",
    "        \n",
    "        ret_list.append(buffer[-1])\n",
    "        return ret_list\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import queue\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root: return []\n",
    "        q, res = queue.Queue(), []\n",
    "        q.put(root)\n",
    "        while not q.empty():\n",
    "            tmp_q = queue.Queue()\n",
    "            right_most = True\n",
    "\n",
    "            while not q.empty():\n",
    "                ptr = q.get()\n",
    "                if ptr.right: tmp_q.put(ptr.right)\n",
    "                if ptr.left: tmp_q.put(ptr.left)\n",
    "                if right_most:\n",
    "                    res.append(ptr.val)\n",
    "                    right_most = False\n",
    "            \n",
    "            q = tmp_q\n",
    "        return res\n",
    "                \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans=[]\n",
    "        query=[root]\n",
    "        while query:\n",
    "            ans.append(query[-1].val)\n",
    "            temp=[]\n",
    "            for q in query:\n",
    "                if q.left:\n",
    "                    temp.append(q.left)\n",
    "                if q.right:\n",
    "                    temp.append(q.right)\n",
    "            query=temp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        ans = []\n",
    "        def dfs(head,level,L):\n",
    "            if head is None:\n",
    "                return\n",
    "            if level == len(L):\n",
    "                L.append(head.val)\n",
    "            dfs(head.right,level+1,L)\n",
    "            dfs(head.left,level+1,L)\n",
    "        dfs(root,0,ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rightSideView(self, root: TreeNode) -> List[int]:\n",
    "        right_value_at_depth = dict() # depth, val\n",
    "        max_depth = -1\n",
    "\n",
    "        stack = [(root, 0)]\n",
    "        while stack:\n",
    "            node, depth = stack.pop()\n",
    "\n",
    "            if node is not None:\n",
    "                max_depth = max(max_depth, depth)\n",
    "\n",
    "                right_value_at_depth.setdefault(depth, node.val)\n",
    "\n",
    "                stack.append((node.left, depth + 1))\n",
    "                stack.append((node.right, depth + 1))\n",
    "        return [right_value_at_depth[depth] for depth in range(max_depth + 1)]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
